package dichotomy.search.number.in.rotate.array;
/**
 * @Time 2020/1/9
 * @author 王光浩 
 * @Need  给出一个原本升序但是在某一个点进行了旋转的整型数组（比如：12345，后变为45123），然后给出一个target
 *       判断在该整型数组中是否存在该target，如果存在返回下标，否则返回-1。（要是时间复杂度O（logn）级别）
 * @Thinking 使用二分法
 *           思路：当previous大于later时，进行特殊的二分法：判断mid与target的大小关系，当mid>target时，判断
 *                 target与previous的大小关系，如果target大于previous那么later=mid-1，否则如果mid大于previous
 *                 则previous=mid+1，否则later=mid-1；当mid<target时，当target大于previous时如果mid大于previous
 *                 那么previous=mid+1，否则later=mid-1，当target小于previous时previous=mid+1。
 *                 当mid<target时，如果target大于previous那么previous=mid+1，否则later
 */
public class MyMethodTwo {
    public int search(int[] nums, int target) {
        int previous=0;
        int later=nums.length-1;
        int mid;
        //使用二分法判断是否存在对应下标
        while(previous<=later) {
        	mid=previous+(later-previous)/2;
        	if(nums[mid]==target)
        		return mid;
        	//不是完全升序状态
        	if(nums[later]<nums[previous]) {
        		if(target>=nums[previous]) {//target在前一个升序数组中
        			if(nums[mid]>target)
        				later=mid-1;
        			else {
        				if(nums[mid]>=nums[previous])
        					previous=mid+1;
        				else
        					later=mid-1;
        			}
        		}
        		else {//target在后一个升序数组中
        			if(nums[mid]<target)
        				previous=mid+1;
        			else {
        				if(nums[mid]>=nums[previous])
        					previous=mid+1;
        				else 
        					later=mid-1;
        			}
        		}
        	}
        	//完全升序状态
        	else {
        		if(nums[mid]>target)
        			later=mid-1;
        		else
        			previous=mid+1;
        	}
        }
        return -1;
    }

}
